In most computer systems, it is desirable to maximize the processing power and throughput of the system hardware. To achieve a higher throughput, a computer system will typically increase the utilization of the hardware by executing multiple processes concurrently. Executing multiple processes concurrently enables a system to enhance its performance by increasing the utilization of the CPU and other peripheral devices.
In a concurrent processing environment, each process is simply an executing program that contains its own program counter, registers and variables. Although concurrent processes often share a disk or common memory area, each process may execute independent of the other processes. Because each process is able to execute independently, events associated with and transactions executed by the concurrent processes can complete asynchronously with respect to one another.
It is often desirable for these otherwise asynchronous events and transactions to be ordered by time of occurrence. For example, tracking the ordering of transactions that perform changes to a database is critical to maintaining the stability and consistency of the database. If data from the database needs to be reconstructed as of a designated time, it is critical to be able to distinguish between changes made by transactions that completed before the designated time and changes made by those transactions that completed after the designated time. Therefore, to maintain consistency, it is extremely important to know when each transaction completed relative to other completed transactions.
One method of ordering events in a multiprocessing system is by assigning a logical time-stamp to each event. For example, as transactions complete in a database system, a logical time-stamp may be attached to each transaction. The logical time-stamp assigned to the completion of each transaction is used by the database system to represent a logical time ordering of when the events occurred.
To effectively assign time-stamps, a mechanism for producing ever-increasing sequence numbers must be provided. A typical method for providing ever-increasing sequence number is to provide a software counter that can be accessed and incremented by each process. Thus, whenever an event occurs for a particular process, the process may increment the software counter, read the counter to obtain a specific sequence number, and attach the sequence number to the current event.
Since logical time-stamps provide only a relative ordering of events, it is not necessary that each sequence number supplied by software counter increment uniformly, but only that the current value provided by the software counter be greater than any previous value provided by the software counter. For example, if events are provided time stamps in the sequence one (1), two (2), five (5), and nine (9), it is still possible to determine the relative order in which each event occurred.
Because the logical time-stamps are relative to one another, it is critical to provide a software counter that will provide ever-increasing numbers throughout the lifetime of the concurrent processing system in which it is used. Therefore, it is often desirable and even necessary, to provide a software counter with a greater range than that provided by the bit-size of a single machine word.
For example, as depicted in FIG. 1, a software counter composed of a single eight-bit machine word can provide only 256 (0 through 255) distinct sequence number values. Once the software counter reaches its maximum value, it will roll over to zero the next time it is incremented. A rollover of the software counter will disrupt the logical time-stamp ordering as the event attached to time-stamp 110 will incorrectly appear to have occurred before the events attached to time-stamps 102-108.
To enable the provision of ever-increasing sequence numbers during the life span of a system, a software counter composed of more than one machine word may be used. For example, as shown in FIG. 2, by dedicating one eight-bit machine word as the base 216 (low order bits) and another machine word as the wrap 202 (high order bits), a software counter can significantly increase its range of valid sequence values and, therefore, substantially increase its effective life span.
It should be noted that FIGS. 1 and 2 depict eight-bit machine words for illustrative purposes only. These examples can easily be extended for computers that employ larger bit machine words, including but not limited to the sixteen or thirty-two bit machines that are commonly in use today. For example, if a thirty-two bit machine is used, a sixty-four bit software counter can be formed by using two thirty-two machine words.
Although utilizing sequence numbers that are multiple machine words long can eliminate the sequence number rollover obstacle in most systems, it has the side effect of introducing yet another problem. Specifically, machine instructions operate on one word at a time. Therefore, a sequence number stored in a software counter that comprises multiple machine words cannot be read or modified in an atomic operation. This gives rise to the possibility that some event may occur between accessing one word of the software counter and accessing another word of the software counter. Consequently, a sequence value obtained by one process may have been corrupted by another process seeking to procure a sequence number from the same software counter at the same time.
For example, if the software counter is comprised of multiple machine words BASE (low order bits) and WRAP (high order bits), two separate read instructions will be required to obtain the complete value. If after reading WRAP, but before reading BASE, another process modifies the software counter, the read instruction will return an incorrect value. Therefore, a process cannot be guaranteed that the returned sequence number is valid.
One technique to guarantee that the sequence number read from a multiple-word software counter will not be corrupted by concurrent processes is to serialize access to the software counter using a latch. Specifically, a latch is established for the software counter. Before a process can access the software counter, the process must obtain the latch. If another process already has the latch, the process must wait until the previous process releases the latch. By obtaining the latch before accessing the software counter, a process ensures that no other concurrently executing process will be concurrently accessing the software counter.
Latching the software counter ensures that the returned sequence number is valid and has not been corrupted by another process. However obtaining a latch can be particularly expensive if the latch is fault-tolerant as the system must retain enough information to be capable of automatically releasing the latch if the process holding the latch dies. Furthermore, allowing only one process at any given time access to a shared resource, such as the software counter, can create a significant bottleneck and, thus, significantly degrade the performance of a high concurrency system.
For example, if process A latches and acquires the shared resource, process B and process C must wait until the latch is released before they can acquire and access to the shared resource. This has the effect of serializing a concurrent system as processes are prohibited from executing until the shared resource is released and they are allowed to latch and access the shared resource themselves.
Additionally, further degradation of a concurrent system occurs when after acquiring a latch on the shared resource, process A is swapped out of memory to allow another process to execute. In this situation, all other processes requiring access to the sequence number must wait until the swapped-out process is rescheduled to execute and releases its latch on the shared sequence generator.
Requiring each process to wait until a latch can be obtained in order to read or modify a software counter has been proven to seriously degrade a database system's performance. Therefore, it is highly desirable for high concurrency systems to minimize the amount of time that a software counter is latched.